Search for: All records

In this article, Momentum Iterative Hessian Sketch (M-IHS) techniques, a group of solvers for large scale linear Least Squares (LS) problems, are proposed and analyzed in detail. The proposed techniques are obtained by incorporating the Heavy Ball Acceleration into the Iterative Hessian Sketch algorithm and they provide significant improvements over the randomized preconditioning techniques. Through the error analyses of the M-IHS variants, lower bounds on the sketch size for various randomized distributions to converge at a pre-determined rate with a constant probability are established. The bounds present the best results in the current literature for obtaining a solution approximation and they suggest that the sketch size can be chosen proportional to the statistical dimension of the regularized problem regardless of the size of the coefficient matrix. The statistical dimension is always smaller than the rank and it gets smaller as the regularization parameter increases. By using approximate solvers along with the iterations, the M-IHS variants are capable of avoiding all matrix decompositions and inversions, which is one of the main advantages over the alternative solvers such as the Blendenpik and the LSRN. Similar to the Chebyshev Semi-iterations, the M-IHS variants do not use any inner products and eliminate the corresponding synchronizations steps in hierarchical or distributed memory systems, yet the M-IHS converges faster than the Chebyshev Semi-iteration based solvers 

We propose a novel randomized linear least squares solver which is an improvement of Iterative Hessian Sketch and randomized preconditioning. In the proposed Momentum-IHS technique (M-IHS), Heavy Ball Method is used to accelerate the convergence of iterations. It is shown that for any full rank data matrix, rate of convergence depends on the ratio between the feature size and the sketch size. Unlike the Conjugate Gradient technique, the rate of convergence is unaffected by either the condition number or the eigenvalue spectrum of the data matrix. As demonstrated over many examples, the proposed M-IHS provides compatible performance with the state of the art randomized preconditioning methods such as LSRN or Blendenpik and yet, it provides a completely different perspective in the area of iterative solvers which can pave the way for future developments.